package 二叉树;

public class No96不同的二叉搜索树 {

    /**
     * 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
     *
     * 示例:
     *
     * 输入: 3
     * 输出: 5
     * 解释:
     * 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
     *
     *    1         3     3      2      1
     *     \       /     /      / \      \
     *      3     2     1      1   3      2
     *     /     /       \                 \
     *    2     1         2                 3
     */

    /**
     * 动态规划: 前1个二叉树能组成不同二叉树的个数->1
     * 左右两边的二叉树相乘 f(0)=1 一边为空,为了保证乘法不出错,就置为1
     * f(1)=1; f(0)*f(0)
     * f(2)=2; f(0)*f(1) f(1)*f(0)
     * f(3)=5; f(0)*f(2) f(1)*f(1) f(2)*f(0)
     * f(4)=14; f(0)*f(3)-5 f(1)*f(2)-2 f(2)*f(1)-2 f(3)*f(0)-5
     * f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-2)*f(1)+f(n-1)*f(0)
     */
    public int numTrees(int n) {

        int[] dp=new int[n+1];
        //base
        dp[0]=1;

        for (int i = 1; i <= n; i++) {
            int count=0;
            for (int j = 0; j < i; j++) {
                count+=dp[j]*dp[i-j-1];
            }
            dp[i]=count;
        }

        return dp[n];
    }

    public static void main(String[] args) {
        No96不同的二叉搜索树 n=new No96不同的二叉搜索树();
        int result = n.numTrees(4);
        System.out.println(result);
    }

}
